package main

import "fmt"

const (
	Width  = 4
	Height = 5
)

const (
	Up = iota
	Left
	Down
	Right
	Limit
)

var maps = [Height + 1][Width + 1]int{
	{0, 0, 1, 0, 0},
	{1, 0, 1, 1, 0},
	{0, 0, 0, 0, 0},
	{1, 1, 1, 0, 1},
	{0, 1, 0, 0, 1},
	{0, 1, 1, 0, 0},
}

type Point struct {
	x, y int
}

var start, end = Point{
	x: 0,
	y: 0,
}, Point{
	x: Width,
	y: Height,
}

func IsValidVal(v int) bool {
	return v != 1
}

func IsValidPos(curPos Point) bool {
	if curPos.x > Width ||
		curPos.x < 0 ||
		curPos.y > Height ||
		curPos.y < 0 {
		return false
	}
	return true
}

func IsNotExistOfInSet(pos Point, posPath []Point) bool {
	for _, v := range posPath {
		if pos == v {
			return false
		}
	}
	return true
}

func BreadthTraversa(curPos Point, prePos []Point) (bool, []Point) {
	if curPos == end {
		return true, prePos
	}
	//遍历四个方向
	l := len(prePos)
	posPath := make([]Point, l+1)
	copy(posPath, prePos)
	for i := Up; i < Limit; i++ {
		nextPos := curPos
		switch i {
		case Up:
			nextPos.y -= 1
		case Left:
			nextPos.x -= 1
		case Down:
			nextPos.y += 1
		case Right:
			nextPos.x += 1
		}
		if IsValidPos(nextPos) &&
			IsValidVal(maps[nextPos.y][nextPos.x]) &&
			IsNotExistOfInSet(nextPos, posPath) {
			posPath[l] = nextPos
			ok, posPath := BreadthTraversa(nextPos, posPath)
			if ok {
				return true, posPath
			}
		}
	}
	return false, nil
}

func main() {
	var tmp []Point
	ok, posPath := BreadthTraversa(start, tmp)
	if ok {
		fmt.Printf("可以走出迷宫！", posPath)
	} else {
		fmt.Printf("无法走出迷宫!")
	}
}
